Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Графы] типичная ли это задача? 
:(
    Опции темы
cupper
Дата 13.5.2013, 17:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 1
Есть задача
Код

Дан ориентированный мультиграф. По его вершинам и рёбрам перемещаются фишки. Две фишки не могут одновременно находиться на одном ребре или в
 одной вершине. Фишка перемещается по графу из вершины в ребро, выходящее из этой вершины; либо из ребра в вершину, в которую входит данное 
ребро. Изначально все фишки находятся в вершинах. Дано некое второе расположение фишек, все фишки также в вершинах. Требуется определить, 
возможен ли на данном графе переход фишек из первого положения во второе.


Пытаюсь найти/понять является ли эта задача типичной задачей на графах, т.е. решение которой уже описано в книгах, или может быть это обобщенная задача, или наоборот урезанный вариант какой то общейзвестной проблемы.

Наиболее похожее что смог найти это задача пятнашки15. Сейчас пытаюсь сообразить эквивалентны ли эти задача.


Это сообщение отредактировал(а) cupper - 13.5.2013, 17:18
PM MAIL   Вверх
Mirkes
Дата 13.5.2013, 20:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 4
Всего: 17
Не эквивалентны. в 15 только одна лакуна а в вашей задаче их много - каждое ребро графа может служить местом, куда спрятали фишку. Хотя что-то общее просматривается. Честно говоря пытался представить ситуацию когда из одного положения нельзя перейти в другое и не смог, кроме одного цикла в котором нужно переставить фишки местами. А вот если к этому циклу добавить хоть одно ребро, то все решается.


--------------------
Mirkes
PM MAIL   Вверх
cupper
Дата 15.5.2013, 07:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 1
После переключения на англоязычную часть интернета удалось найти один тред в котором идем разговор о сходстве этой задачи с задачей сокобан. 
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.

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

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


 




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


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

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