Модераторы: Poseidon
  

Поиск:

Закрытая темаСоздание новой темы Создание опроса
> Путь Гамильтона в графе, гамильтон, путь, hamiltonian, path 
:(
    Опции темы
sas8899
Дата 22.12.2007, 02:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 28
Регистрация: 27.10.2007

Репутация: нет
Всего: нет
Муравей снабжается набором простых правил, которые позволяют ему выбирать путь в графе. Он поддерживает список табу (tabu list), то есть список узлов, которые он уже посетил. Таким образом, муравей должен проходить через каждый узел только один раз. Путь между двумя узлами графа, по которому муравей посетил каждый узел только один раз, называется путем Гамильтона (Hamiltonian path) http://en.wikipedia.org/wiki/Hamiltonian_path
Муравей должен пройти через каждый узел в графе, если это ему удается, то значит в графе существует цикл Гамильтона, тоесть вернуться откуда начал. Граф выражается в форме матрицы, элементы которой равны 1 если i связан с j  и 0 если не связан.

Заранее спасибо. 
PM MAIL   Вверх
Kuvaldis
Дата 22.12.2007, 03:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61

M
Kuvaldis		Некорректна формулировка: нужна программа на каком-нибудь языке или алгоритм?



--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
sas8899
Дата 22.12.2007, 19:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 28
Регистрация: 27.10.2007

Репутация: нет
Всего: нет
Kuvaldis, вот что я нашел, но не понимаю как она действует
Код

void extend (int i)
{
for (j \in neighbourhood(path[i]))
if (used[j] == false)
{
path[i+1] = j;
used[j] = true;
if (i+1 == n)
{
output (path);
stop ();
}
else
extend (i+1);
used[j] = false;
}
}

void main (void)
{
for (i=1; i<=n; i++)
used[i]=false;
for (i=1; i<=n; i++)
{

Благодарен за любую помощь.
PM MAIL   Вверх
  
 Закрытая темаСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0625 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.