Algorithm frage; ich brauch eure hilfe...

Green_Ghost

Tach;

Ich mache an einem Wettbewerb mit. Da muss man 6 Aufgaben zu hause loesen.
Die ersten 4 algo Aufgaben waren kein Problem.
Aber nun sind die letzten 2 Aufgaben etwas schwieriger.

Ich will nicht, das ihr sie fuer mich loest! Da hab ich ja dann nichts gelernt.
Ich brauche nur einige Links, Ideen und Starthilfen.

Ich nehme an das man beide Aufgaben mit dem Dijkstra Algo loessen muss.
Nach dem Dijkstra algo habe ich etwas gegooglet, und nach 3h habe ich
ich etwas wie ein grafen geschaft. Ob das stimmt?

std::map<std::string, std::map<std::string, int> > grafen;
grafen["japan"]["amerika"]=12;
grafen["japan"]["kanada"]=9;
garfen["amerika"]["japan"]=12;
grafen["amerika"]["kanada"]=4;
//...

Mehr konnte ich aus den Formeln und dukus nicht zusammen reimen!

Also Die 1 Aufgabe:
http://www.soi.ch/php/do.php?d=contest/2005/round1/tasks/obelixsuchtidefix/desc.html&l=d
Meine gedanken:
-Dijkstra als algo?
-Wie stellt man das in einem z.B. vector da...

Die 2 Aufgabe:
http://www.soi.ch/php/do.php?d=contest/2005/round1/tasks/pacman/desc.html&l=d
Meine gedanken:
-wieder der Dijkstra?

Das beste ist wohl, wenn man wircklich den Dijkstra braucht, das ich ihn zu erst lerne. Kann mir jamand helfen?
Ich habe leider kein Geld, da ich erst gerade 17 geworden bin, und das alles
ein Hobby ist und ich noch zur schule gehe.
Aber dieser Wettberwerb hat mich gereitzt, und was ich nicht kann, will ich
koennen ^^'.

Nochmals, ich will nicht das ihr fuer mich die aufgeben loest.

MFG Ghost

ness

http://de.wikipedia.org/wiki/Dijkstras_Algorithmus
Aber wie kommst du darauf, dass du grad Dijkstra willst? Gibt doch noch mehr Wegsuchelgos?

Green_Ghost

Es gibt mehr als einen Short Path algo?
Kannst du mir helfen, und sagen welchen ich am besten lernen sollte,
um diese Aufgaben loesen zu koennen?
Ich habe nur von Dijkstra gehoert.

ness

Mir fällt jetzt auf anhib noch A* (http://de.wikipedia.org/wiki/A*-Algorithmus) ein.
Am ehesten wirst du wohl hier fündig, such dir einfach was raus, was dir einfach umsetzbar erscheint: http://de.wikipedia.org/wiki/Kategorie:Graphentheorie
Btw:

Green_Ghost

--Ueberarbeitet--

Green_Ghost

Habe gerade ein gutes Manual gefunden.
Werde es posten wenn ichs geschaft habe...

Green_Ghost

Habe jetzt den Dijkstra Algo genommen.
Hab ihn gelernt und studiert.

Hier mein code mit main:

Main:

int main(){
  Graph test;
  test["japan"]["usa"]=12;
  test["usa"]["kanada"]=14;
  test["usa"]["kuba"]=3;
  test["kuba"]["kanada"]=4;

  Nodelist strecke;

  dijkstra(test, "japan", strecke);

  Nodelist::iterator it;
  for(it=strecke.begin(); it!=strecke.end(); ++it){
    std::cout<<it->second<<" <=> "<<it->first<<std::endl;
  }
  return 1;
}

Dijkstra function:

#include <map>
#include <string>
#include <utility>
#include <functional>
#include <queue>
#include <vector>
#include <iostream>

typedef std::string Nodelabel;
typedef std::map<Nodelabel, int> Nodelist;
typedef std::map<Nodelabel, Nodelist> Graph;
typedef std::pair<Nodelabel, Nodelist> Node;
typedef std::pair<int, Nodelabel> Edg;

bool operator>(const Edg r, const Edg k){ return r.first>k.first; }

void dijkstra(Graph &graph, Nodelabel source, Nodelist &distance){
  distance.clear();
  std::priority_queue<Edg, std::vector<Edg>, std::greater<Edg> > que;
  que.push(Edg(0, source));

  while(!que.empty()){
    Edg tmped=que.top();
    Nodelabel tmpnl=tmped.second;
    que.pop();
    if(distance.count(tmpnl)==0){
      int dist=tmped.first;
      distance[tmpnl]=dist;
      Nodelist tempgraph=graph[tmpnl];
      Nodelist::iterator it;
      for(it=tempgraph.begin(); it!=tempgraph.end(); ++it){
        int distint=it->second;
        Nodelabel distlabel=it->first;
        que.push(Edg(dist+distint, distlabel));
      }
    }
  }
}

Ausgabe:

# ./algo
20 <=> australien
27 <=> europa
0 <=> japan
19 <=> kanada
15 <=> kuba
12 <=> usa

Der Dijkstra algo rechnet bekanntlich von einem knotten zu allen.
Natuerlich immer der k. Weg.

Nun moechte ich z.B. von Knotte japan nach knotte kanada.
Und dann den weg ausgeben. also(japan > usa > kuba > kanada)
Ich bin auf zwei loesungen gekommen, wie man das machen koennte:

Ich loesche alle Knotten die nicht zu knotte ziehl kommen.

oder/und?

Ich mache aus map<string, int> ein map<string, pair<int, stack>
und lese dann den weg aus dem stack. wuerde aber viel RAM fressen,
bei vielen knotten.

Welche loesung waehre wohl eure meinung nach am besten?
Hat mir jemand einen TIPP? oder eine ergaenzung?

Danke, Ghost

Gast221212

Green_Ghost schrieb:

Habe jetzt den Dijkstra Algo genommen.
Hab ihn gelernt und studiert.

Danke, Ghost

Ich würde das ganze wohl mit einem "Minimum Spaning Tree (Kruskal's algorithm)" lösen (Der gibt die kurzesten Wege zu allen anderen Feldern an). Und dann den Weg von O nach I suchen.

Green_Ghost

Betreff Kruskal's algorithm.
Kannst du mir sagen, was daran besser geeignet ist?
Die vorteile?

hat jemand eine Idee, wie man aus einer zeile, ein "kreis" machen
kann, und dies in einen graphen oder vector einliest?

Also:

aus: kpLMNOqRSTUV
das:
  NMLV
  OkpU
  qRST

// Gibt es irgeind eine Formel?
//wenn ich das richtig verstanden habe...

Gast221212

Green_Ghost schrieb:

Betreff Kruskal's algorithm.
Kannst du mir sagen, was daran besser geeignet ist?
Die vorteile?

Der ist halt trivial

Green_Ghost schrieb:

hat jemand eine Idee, wie man aus einer zeile, ein "kreis" machen
kann, und dies in einen graphen oder vector einliest?

Also:
aus: kpLMNOqRSTUV
das:
  NMLV
  OkpU
  qRST

// Gibt es irgeind eine Formel?
//wenn ich das richtig verstanden habe...

ich erkenne leider kein System in aus und das

Green_Ghost

Die Formel konnte ich errechnen.

zl/y=x und zl/x=y wobei y=x-1
daraus ist start
array[m][m] im weiteren array[m][m+i] und array[m+i][m+i]
wobei array[m][m-i] und array[m-i][m-i] je nach verlaufsort.

leider hab ich gemarkt, dass das nicht die Frage ist, weil der graf
m=1
m=2
m=3
m=4
m=5
also ein 5eck graf ist. Aber bald habe ich es, glaube es zumindest.
Suche jetzt auf der "Wunderkarte" eine gemeinsamkeit, also sowas wie
m=m+x
m=m*x-y
...

Ghost