Найти наименьшую цепочку...

← →
RustamK (2007-01-31 05:10) [0]

Здравствуйте Мастера! Есть в народе такая игра "Города", немного о правилах. Одним из участников называется какой-либо город (напр. Минск), следующий игрок должен назвать город начинающийся на букву на которую заканчивается предыдущийся названный город (надеюсь понятно:), вобщем следующий город в нашем примере должен быть на букву К и так по цепочке пока кто-нибудь не сможет назвать очередной город. Теперь внимание вопрос! Имея список городов (города беруться только из этого списка), как узнать вариант игры с самой короткой цепочкой?

← →
Alex Konshin © (2007-01-31 05:28) [1]

До сих пор зачет не получен?

← →
RustamK (2007-01-31 05:52) [2]

Да не то чтобы зачет... Но хочется отгадку на эту загадку:)

+ к [0]: если название города заканчивается на ь, ъ, й берется предпоследняя буква.

Намекните хоть как это решить

← →
Separator © (2007-01-31 08:40) [3]

Самая короткая цепочка -это 2 города, а самая длинная - все города из списка, так вот берешь 1 город и ищеш следующий подходящий для него город, если такового не найдено, то берешь следующий город по циклу и ищеш для него, как только составлена цепочка из двух городов, то решение значит найдено и таких цепочек может быть много, значит и ответов тоже много

← →
колхоз глазами хакера (2007-01-31 08:51) [4]

> Самая короткая цепочка -это 2 города
Алма-Ата -- цепочка из одного города. ;-)

← →
Павел Калугин © (2007-01-31 09:09) [5]

> [0] RustamK (31.01.07 05:10)

наверное построить соотвествующй граф и найти наикратчайший путь в нем?

← →
Separator © (2007-01-31 09:12) [6]

Алмат-Ата - такого города сейчас в нашем мире нет вот уже более 15 лет, есть город Алматы

← →
Vlad433 © (2007-01-31 11:04) [7]

Недавно была такая задачка. Перебором решается. И рекурсивной процедурой.

← →
TUser © (2007-01-31 11:07) [8]

С каких пор кратчайшие пути в графе ищутся перебором?

Автор уточни условия. Что значит - "самая короткая"? Которую нельзя больше продолжить. Ищи город, дальше которого ничего не бывает, потом присобачь к нему спереди что-нибудь подходящее - вот тебе и ответ.

← →
Vlad433 © (2007-01-31 11:09) [9]

Может быть и нет такого города. А если есть, зачем к нему спереди присобачивать ? С него и начинать тогда.

← →
partizan (2007-01-31 11:11) [10]

Наверно имеется ввиду цепочка, чтоб первая буква первого слова и последняя буква последнего совпадали, тоесть кратчайший цикл в графе.

Ищется поиском в глубину

← →
Vlad433 © (2007-01-31 11:16) [11]

Вроде по условию - пока цепочка не закончится. То есть нет слова на эту букву или оно уже было использовано.

← →
partizan (2007-01-31 11:25) [12]

Тогда из каждой вершины - поиск в ширину, до 1-й вершины, из которой уже некуда будет идти. Из всех таких цепочек выбираем минимальную

← →
TUser © (2007-01-31 11:39) [13]

> partizan (31.01.07 11:25) [12]

Лучше искать назад - от вершины, дальше котоорой идти нельзя.

← →
RustamK (2007-01-31 11:41) [14]

> Автор уточни условия. Что значит - "самая короткая"? Которую
> нельзя больше продолжить.

В списке нет подходящих городов (из не названных)

← →
RustamK (2007-01-31 11:45) [15]

> Самая короткая цепочка -это 2 города, а самая длинная -
> все города из списка, так вот берешь 1 город и ищеш следующий
> подходящий для него город, если такового не найдено, то
> берешь следующий город по циклу и ищеш для него, как только
> составлена цепочка из двух городов, то решение значит найдено
> и таких цепочек может быть много, значит и ответов тоже
> много

Важно не количество ответов с наименьшей цепочкой, а именно длинна наименьшей цепочки.
Цепочка из 2-х городов понятно что самая короткая (хотя может быть и из одного города...), но из списка в 5000 городов навряд ли получится самой короткой

← →
partizan (2007-01-31 11:47) [16]

> Лучше искать назад - от вершины, дальше котоорой идти нельзя.

Что значит "вершина, дальше котоорой идти нельзя"?

← →
RustamK (2007-01-31 11:50) [17]

> Vlad433 © (31.01.07 11:04) [7]
> Недавно была такая задачка. Перебором решается. И рекурсивной
> процедурой.

Тоже думаю перебором, но кажеться что долго будет...

> partizan (31.01.07 11:11) [10]
> Наверно имеется ввиду цепочка, чтоб первая буква первого
> слова и последняя буква последнего совпадали, тоесть кратчайший
> цикл в графе.Ищется поиском в глубину

Может это выглядет глупо, но всё же... Что такое граф? И как искать в нем в глубину?

← →
Vlad Oshin © (2007-01-31 11:53) [18]

а что к графу привязались..

имхо
заводим массив с оценкой окончания города.
Берем город, с минимальной оценкой.
1
преоцениваем оставшиеся, из всех городов удовлетв. игре берем город с минимальной оценкой. goto 1

← →
Vlad433 © (2007-01-31 11:53) [19]

>TUser
Назад, вперед - какая разница. Согласен, что перебор не идеален. А как по-другому ?

← →
Думкин © (2007-01-31 11:54) [20]

RustamK (31.01.07 11:45) [15]

Рустамчик, ты бы все-таки напрягшись для начала попробовал дать задачку в более четких рамках. Чего ты хочешь - пока загадка.

Почему наврядли и т.п.?

← →
Vlad433 © (2007-01-31 11:57) [21]

Да вроде условие понятно. Только говорят что перебором долго. Если список несколько тысяч - согласен. Может и есть оценочные решения, но конкретно методику вроде никто пока не описал.

← →
Vlad433 © (2007-01-31 11:59) [22]

Пока "хороших" решений нет, предлагаю написать перебором и оценить время.

← →
Думкин © (2007-01-31 12:00) [23]

Vlad433 © (31.01.07 11:57) [21]

После уточнения - да. А я его не увидел. Теперь - да.

← →
RustamK (2007-01-31 12:00) [24]

RustamK (31.01.07 11:45) [15] Почему наврядли и т.п.?

Потому что в списке нет такой цепочки, чтобы она закончилась на 2-ом городе, и нельзя было назвать 3-й...

← →
Vlad Oshin © (2007-01-31 12:03) [25]

вообще то нет...

← →
Думкин © (2007-01-31 12:13) [26]

В игре участвует 30 буков. Причем внутренние буковы неинтересны.
Соответственно имеем 900 групп фишек, с разным количеством в группе.
После каждой фишки мы можем поставить одну из 30 групп фишек.
Группы фишек опять же можно сгруппировать - например все, что начинаются на одну и ту же букву или заканчиваются, что впрочем симметрично для поиска решения.
Дальше пока не знаю. :)

← →
partizan (2007-01-31 12:22) [27]

> Пока "хороших" решений нет, предлагаю написать перебором
> и оценить время.

Чем плохо:

> Тогда из каждой вершины - поиск в ширину, до 1-й вершины,
> из которой уже некуда будет идти. Из всех таких цепочек
> выбираем минимальную

?

Легко получить оценку на самую короткую цепочку снизу.

Группируем фишки по группам в которых фишки заканчиваются на одну букву. Смотрим количества.
Группируем фишки по группам в которых фишки начинаются на одну букву. Смотрим количества.

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

2 Думкин :)
тоже примерно так думал выше

список городов -> CityList:array of record a:byte начало , b:byte конец end;
ozenka: array of longint, где ozenka[i] = сколько всего городов заканчиваются также

или еще одна оценка,
ozenka2: array of longint, где ozenka2[i] = сколько всего городов начинаются также

стратегия брать город с минимумом оценки.

Думкин
Честно говоря, не понял, как конкретно решается задача. Сгруппировали. Посчитали буквы с начала, с конца. Сопоставляем пары (начальные с конечными ?). Как решать-то ?

+ пересчитывать оценки после каждого выбора города

> [17] RustamK (31.01.07 11:50)

есть такой предмет "теория графов и комбинаторный анализ" Область изучения - подобные задачи.
Данная задача сначала решается карандашем на бумаге.

Vlad433 © (31.01.07 12:36) [30]

Очень сложно понять то, что и не пытались объяснить. Я черным по русскому написал, что

Дальше пока не знаю. :)

Это доступно?

RustamK
Какое максимальное значение городов в списке ?

> Я черным по русскому

а вдруг у него расцветка не такая :)

зы
все, сюда не ходок. Сейчас решите, а я сам хотел бы ... :)

Vlad Oshin © (31.01.07 12:54) [35]
Не, решать вряд ли кто будет с выкладыванием решения. К тому же нижняя оценка еще более уточняется и в общем случае поднимается. Оценить бы сверху...

← →
RustamK (2007-01-31 13:04) [37]

> Что за значение?

Ну максимально в списке сколько. Если в разумных пределах (100-200) то перебором и голову не ломать :)

← →
RustamK (2007-01-31 13:14) [39]

Найти наименьшую цепочку... Найти похожие ветки