|
|
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
Кордон. Дана система дорог. Известно что преступник скрывается в городе A. Нужно не дать ему попасть в города B1, B2 и B3. Каково минимальное количество дорог, которое нужно перекрыть? Искал везде, но не нашел, нашел только вот эту задачу.До этого даже незнал как называется она. плиз,может кто встречался. хотя бы какой метод использовать. Пробовал много чего. Такое ощущение что кроме полного перебора ничего неподойдет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2009, 13:36:11 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
КордонКордон. Дана система дорог. Известно что преступник скрывается в городе A. Нужно не дать ему попасть в города B1, B2 и B3. Каково минимальное количество дорог, которое нужно перекрыть? Здесь уточню. Для меня хватит только один город. Например чтоб из А в В1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2009, 13:37:45 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
Хотя бы более точное название задачи, чтоб поискать можно было. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2009, 18:04:56 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
Это потому что Вы априори поставили себя в А и теперь пытаетесь найти все пути, которые ведут в В1. А Вы поставьте себя в Б1. Вам же известны все дороги, которые ведут в В1. Ну и перекройте их. Тогда преступник гарантированно не сможет попасть в В1 ни из какого другого города. Вот и всё. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2009, 19:42:42 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
mikhail_n, Спасибо. Но мне кажется задачу ты непонял. Надо перекрыть минимальное кол-во дорог. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2009, 19:46:12 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
Кордонmikhail_n, Спасибо. Но мне кажется задачу Вы непоняли. Надо перекрыть минимальное кол-во дорог. Хотел так написать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2009, 19:47:16 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
Ну тогда проверяйте все дороги которые ведут в В1 на предмет можно ли по ним попасть в А. Если да, то прекрывайте. Это перебор, но не полный. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2009, 19:49:27 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
Один вариант есть. 1.Найти все циклы где присутствуют Пункт1 и Пункт2, и посчитать какая из ребер использовалась макс.кол-во раз. 2. Удалить ребро.(если несколько то любое) 3. повторить шаг 1. Все повторять пока получаются циклы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2009, 20:43:14 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
Это вырожденная задача "о минимальном сечении графа" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.02.2009, 01:08:06 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
КордонИскал везде, но не нашел, нашел только вот эту задачу. Искать в исследовании операций (это дисциплина такая математическая). Мало интересовался, но это вырожденный случай задачи, которую при мне решали (транспортная сеть, задача - отбомбить её с требуемым ухудшением пропускной способности, ну и соответственно - строить сеть, минимально теряющую пропускную способность при заданном уровне повреждений). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.02.2009, 12:59:37 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
Кстати, насчет перебора... Метод Форда-Фолкерсона -- это оно и есть, с одной мааааленькой поправкой: это сильно усеченный перебор. Настолько сильно, что сложность его полиномиальна. :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.02.2009, 16:13:12 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
По идее если взять алгоритм А* и попробовать его для Вашего случая переработать. То имхо должно помочь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.02.2009, 00:17:29 |
|
||
|
Задача Кордон
|
|||
|---|---|---|---|
|
#18+
Вот примерно так(Вершины - пути, ребра - дороги): 1) Удалаяешь, если есть ребро(А, Б). 2) THEEND=true; 3) Находишь все маршрутах от А до Б. Для каждого ребра ведешь подсчет в скольких маршрутах оно встречалось. Для каждой вершины тоже ведешь подсчет. Если кол-во маршрутов = 0, то THEEND = false 4) Находишь вершину которая встречается максимальное кол-во раз(Врешины А и Б не считать). 5) у этой вершины находишь ребро, которое встречается макс.кол-во раз.(все это мы учитывали когда искали маршруты).Если макс.ребер несколько, то проверяешь у какого ребра второй пункт встречается макс. кол-во раз. Удаляешь это ребро 6) Если THEEND=true то переходишь на шаг 3. 7) Выводишь результат ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.02.2009, 10:19:37 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=35813518&tid=1344662]: |
0ms |
get settings: |
9ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
42ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
49ms |
get tp. blocked users: |
1ms |
| others: | 258ms |
| total: | 391ms |
| 0 / 0 |
