[algorytmika] - geez, jak to ugryzc?!

0

Prosze o pomoc w rozwiazaniu nastepujacego problemu...

wyobrazmy sobie siec komnat w zamku. Powiedzmy ze komnat jest kilkaset. Miedzy soba polaczone sa korytarzami. Z jednej komnaty moze wybiegac wiele korytarzy (albo zaden). Kazda komnata ma przyporzadkowana zmienna y (wartosci moga sie powtarzac). Jedna z komnat jest komnata poczatkowa, inna koncowa (ich y rowne sa zero)

Teraz rozwazmy nastepujacy problem:
Wyobrazmy sobie pionka ktory zaczyna w komnacie poczatkowej. Na starcie ma przypisana zmienna x = np. 1000. Przechodzac przez komnate od x trzeba odejac y komnaty. Nalezy napisac program, ktory obliczy jak ma po tych komnatach chodzic, aby skonczyc w komnacie koncowej, w dodatku z x rownym dokladnie 0.

:-0

Z gory BARDZO dzieki za pomoc...

0

czy to nie było przypadkiem kiedyś na OI ??

PS. Jeżeli tak to wypadałoby napisać...

0

czy to nie było przypadkiem kiedyś na OI ??

PS. Jeżeli tak to wypadałoby napisać...

Calkiem mozliwe - nie wiem, dostalem w pakiecie od nauczyciela infy :).

0

Tak sie tylko spytam. Czy mozliwe jest odwiedzanie juz odwiedzonych komnat? Jesli tak, to czy dozwolone sa drogi z danej komnaty do siebie samej?

0

Tak sie tylko spytam. Czy mozliwe jest odwiedzanie juz odwiedzonych komnat? Jesli tak, to czy dozwolone sa drogi z danej komnaty do siebie samej?

Mozna odwiedzac komnaty kilkukrotnie. Nie istnieja drogi z danej komnaty do niej samej :)

0

Całość zapisujesz w postaci grafu - jeżeli istnieje krawędź a->b, to jej waga wynosi koszt b, a koszt b->a wynosi koszt a.

Dla tak skonstruowanego grafu wystarczy zrobić proste przeszukiwanie w głąb z nawrotami (zaczynając od komnaty początkowej), zapamiętując na stosie numer komnaty w której się znajdujesz, dodatkowo cofasz się, gdy x==0, a jeszcze nie jesteś na końcu. Podczas cofania, usuwasz numer komnaty ze stosu.

Ponieważ jesteś ograniczony ze względu na x, nie musisz bać się o nieskończone cykle.

0

Całość zapisujesz w postaci grafu - jeżeli istnieje krawędź a->b, to jej waga wynosi koszt b, a koszt b->a wynosi koszt a.

Dla tak skonstruowanego grafu wystarczy zrobić proste przeszukiwanie w głąb z nawrotami (zaczynając od komnaty początkowej), zapamiętując na stosie numer komnaty w której się znajdujesz, dodatkowo cofasz się, gdy x==0, a jeszcze nie jesteś na końcu. Podczas cofania, usuwasz numer komnaty ze stosu.

Ponieważ jesteś ograniczony ze względu na x, nie musisz bać się o nieskończone cykle.

eee... aha... chyba brakuje mi podstaw z zakresu algorytmiki i struktur danych... Wroce do zadania jak bede wiedzial co to jest graf albo "przeszukiwanie w glab z nawrotami" ;)

0

można zaprząc do tego algorytm genetyczny, który dąży do tego aby wynik były równy zero.

0

aha, jeśli chodzi o podstawy algorytmiki - poczytaj moj art na <url>hardheads.prv.pl</url> :P</url>

0

Zrobilem tak jak juz ktos napisal - przeszukiwanie grafu z nawrotami. Wszystko pieknie dziala - dzieki za pomoc.

(ps. A co do algorytmow genetycznych, to to chyba troszke za trudne jak dla mnie :-) )

0

Zrobilem tak jak juz ktos napisal - przeszukiwanie grafu z nawrotami. Wszystko pieknie dziala - dzieki za pomoc.

To jest najprostrze (chyba) rozwiązanie. Na dodatek implementacja też jest bardzo prosta :P

0

można zaprząc do tego algorytm genetyczny, który dąży do tego aby wynik były równy zero.

Oj niekoniecznie - algorytmy genetyczne nie daja pewnosc ze otrzymamy konkretny wynik - stosuje sie je raczej jak mamy zminimializowac (lub zmaxymalizowac) funkcje celu a nie otrzymac jej konkretna wartosc - w takim wypadku trzeba zastosowac jakis deterministyczny algorytm przeszukujacy cala przestrzen stanow az do osiagniecia rozwiazania ( czyli np. algorytm z nawrotami )

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