1 Востаннє редагувалося Param (19.02.2013 13:59:22)

Тема: Задачка з обласноі олімпіади

http://loippo.lviv.ua/fusion/uploads/ol … ements.pdf
Ось посилання на задачу. 2 задача підскажіть як її розв'язати, тому що навіть ідей не маю з чого ж почати.

Re: Задачка з обласноі олімпіади

Офтоп:
Але формулювання задач - ржака :D

3

Re: Задачка з обласноі олімпіади

Прихований текст
Зеник молодець.

А по темі, пошукайте в гуглі задачу комівояжера. Йти на олімпіаду і не знати типових задач.

4

Re: Задачка з обласноі олімпіади

Vo_Vik написав:
Прихований текст
Зеник молодець.

А по темі, пошукайте в гуглі задачу комівояжера. Йти на олімпіаду і не знати типових задач.

Аж ніяк. Треба знайти всі цикли (DFS, BFS на вибір), і вибрати мінімальну вершину що входить в якийсь з циклів.

5

Re: Задачка з обласноі олімпіади

Ну може, я там детально не розбирався, але з тої опери.

6

Re: Задачка з обласноі олімпіади

bunyk написав:
Vo_Vik написав:
Прихований текст
Зеник молодець.

А по темі, пошукайте в гуглі задачу комівояжера. Йти на олімпіаду і не знати типових задач.

Аж ніяк. Треба знайти всі цикли (DFS, BFS на вибір), і вибрати мінімальну вершину що входить в якийсь з циклів.

А можна якесь посилання або інформацію на вище названі цикли

7

Re: Задачка з обласноі олімпіади

Копати теорію графів і глибше. Почавши з вивчення термінів.

DFS (Depth First Search) - пошук у глибину.
BFS (Breadth First Search) - пошук в ширину.

Якщо в двох словах, то в обох алгоритмах ми заводимо список відвіданих вершин. Додаємо туди першу вершину. У BFS при опрацюванні вершини додаємо всі суміжні з нею невідвідані до кінця списку. У DFS - додаємо першу що попалась, і починаємо опрацьовувати її.

Як тільки ми бачимо відвідану вершину що є суміжною з тою що опрацьовується - ми зустріли цикл.

Подякували: Param1