Jaki algorytm??

Odpowiedz Nowy wątek
2007-11-25 12:33

Rejestracja: 14 lat temu

Ostatnio: 12 lat temu

0

Witam
Z przedmiotu "Algorytmy i struktury danych" dostałem następujący projekt do wykonania:

Napisać program znajdujący przejście przez zadaną planszę. Plansza składa się z dróg i komnat, które reprezetują skrzyżowania. Do każdej komnaty można wejść tylko jeden raz.

Co do algorytmu, to myślałem że użyję tutaj algorytmu Prima lub Kruskala, które operują na grafach, ale raczej to odpada. Jaki algorytm mogę użyć do wyznaczenia tej drogi??

Pozostało 580 znaków

lamus
2007-11-25 17:31
lamus
0

cykl hamiltona ;) lub droga hamiltona

Pozostało 580 znaków

2007-12-07 10:47

Rejestracja: 17 lat temu

Ostatnio: 3 miesiące temu

0

ogolnie problem komiwojazera - jest duzo algorytmow


Pozostało 580 znaków

2007-12-07 12:17

Rejestracja: 16 lat temu

Ostatnio: 7 lat temu

0

Ani cykl hamiltona ani problem komiwojażera. Nie jest powiedziane, że:

  • trzeba wejść do każdej komnaty (cykl hamiltona, problem komiwojażera)
  • ma to być najkrótsza droga (problem komiwojażera)
  • musimy wrócić do punktu startowego (cykl hamiltona)

Problem rozumiem w ten sposób, że mamy znaleźć dowolną drogę w jak najkrótszym czasie.
Wydaje mi się, że DFS będzie dość szybki.

wisnia01: popraw temat, przynajmniej dopisz, że o graf chodzi.

Pozostało 580 znaków

2007-12-08 13:25

Rejestracja: 17 lat temu

Ostatnio: 3 miesiące temu

0

@adf88
w sumie racja:D
a w takim razie propnuje algorytm Dijkstry


Pozostało 580 znaków

2007-12-08 16:45

Rejestracja: 16 lat temu

Ostatnio: 7 lat temu

0
Johny_Morfina napisał(a)

@adf88
w sumie racja:D
a w takim razie propnuje algorytm Dijkstry
Heh, ale algorytm Dijkstry też szuka najkrótszej drogi

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0