Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Есть ли полный алгоритм поиска пути без перебора вариантов путей?
Да 33%  33%  [ 1 ]
Нет 66%  66%  [ 2 ]
Всего голосов : 3
Автор Сообщение
 Заголовок сообщения: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 12:15 
Не в сети
Начинающий
Зарегистрирован:
10 сен 2019, 11:52
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Привет!

Наткнулся на такую задачу. Оказалась очень занимательной,

Дана таблица 10х10, заполненная повторяющимися числами от 1 до 33.
Требуется найти путь от 1 до 33, проходящий через все 33 числа ровно по 1му разу.
По диагонали двигаться не разрешается.

115222414171015432
6418202681991811
32921232111512417
12291329152822233121
2715241211610282731
2623222628273041017
242019101571623921
424261582725103129
232217253232220519
17313217287151233


Путь я нашел, но не без перебора.
Автором такого класса задач по всей видимости является Л.П. Мочалов, но в его книге алгоритм только на тривиальные задачи.

Вопрос: Как максимально математизировать эту задачу, чтобы минимизировать перебор?
Думал про теорию графов и линейную алгебру.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 14:34 
Не в сети
Гений
Зарегистрирован:
02 июн 2018, 08:50
Сообщений: 659
Cпасибо сказано: 21
Спасибо получено:
105 раз в 103 сообщениях
Очков репутации: 16

Добавить очки репутацииУменьшить очки репутации
Elia писал(а):
Требуется найти путь от 1 до 33, проходящий через все 33 числа ровно по 1му разу.

А путь должен быть по числам следующим в порядке возрастания 1-2-3...33 или в любом порядке, лишь бы по разу на каждом из чисел?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 14:57 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
924 раз в 873 сообщениях
Очков репутации: 131

Добавить очки репутацииУменьшить очки репутации
Emphatic18 писал(а):
А путь должен быть по числам следующим в порядке возрастания 1-2-3...33?

Это невозможно при заданных значениях и было бы тривиально, если бы было возможно.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Booker48 "Спасибо" сказали:
Elia
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 15:06 
Не в сети
Гений
Зарегистрирован:
02 июн 2018, 08:50
Сообщений: 659
Cпасибо сказано: 21
Спасибо получено:
105 раз в 103 сообщениях
Очков репутации: 16

Добавить очки репутацииУменьшить очки репутации
Алгоритм Дейкстры здесь нельзя применить?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 15:08 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
924 раз в 873 сообщениях
Очков репутации: 131

Добавить очки репутацииУменьшить очки репутации
Elia
В голову лезет волновой алгоритм, очень ресурсожоркий. Но ничего лучшего не могу предложить. И он, вроде бы, должен закончиться за 33 шага.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 20:30 
Не в сети
Начинающий
Зарегистрирован:
10 сен 2019, 11:52
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Emphatic18 писал(а):
Алгоритм Дейкстры здесь нельзя применить?

Я не додумал как сформулировать задачу, в особенности - ограничения, в графах. Вершин брать 100 или 33, если 33 - то как ребра занумеровать и как отметить, что в зависимости от того, из какой вершины попал в текущую, доступна только часть маршрутов. А если брать 100 вершин как применять алгоритм, чтобы определять ненужные вершины?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 20:35 
Не в сети
Начинающий
Зарегистрирован:
10 сен 2019, 11:52
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Booker48 писал(а):
Elia
В голову лезет волновой алгоритм, очень ресурсожоркий. Но ничего лучшего не могу предложить. И он, вроде бы, должен закончиться за 33 шага.


Спасибо, про волновой алгоритм кстати не подумал. Но он по сути как полный перебор будет?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 21:11 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
924 раз в 873 сообщениях
Очков репутации: 131

Добавить очки репутацииУменьшить очки репутации
Elia писал(а):
...про волновой алгоритм кстати не подумал. Но он по сути как полный перебор будет?

Не совсем. Мне кажется, что на такой структуре, как таблица, будут эффективно отсекаться "лишние" трассы, как только волна дойдёт до числа, которое уже содержится в трассе (как при пересечении существующей трассы, так и при обработке новой клетки). Но количество трасс растёт, конечно, быстро. Надо бы помоделировать, да мне долго это писать, хотя он и не сложен в реализации. )))

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 11 сен 2019, 12:35 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
924 раз в 873 сообщениях
Очков репутации: 131

Добавить очки репутацииУменьшить очки репутации
Подумал немного: волновой алгоритм идеально применим к этой задаче. Полного перебора не будет, волну надо запускать от двойки (2), поскольку она ровно один раз встречается в таблице и точно войдёт в решение, если оно вообще существует.
Но даже если бы все числа входили в таблицу более одного раза (допустим, 3, чаще не получится по причинам общего количества клеток и чисел), то решение было бы получено максимум после запуска третьей волны.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 9 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Занимательная задачка

в форуме Начала анализа и Другие разделы школьной математики

YchenikMonaxa

7

316

18 фев 2023, 12:53

Занимательная математика

в форуме Алгебра

vvd

13

714

04 май 2015, 02:25

Занимательная чушь

в форуме Палата №6

fibona

18

1045

16 июл 2019, 18:06

Занимательная стереометрических задача

в форуме Геометрия

Lechka

9

288

23 окт 2022, 11:34

Занимательная задача по геометрии

в форуме Интересные задачи участников форума MHP

Buratino

30

1040

26 фев 2022, 23:43

Занимательная задача про переустановку колес

в форуме Интересные задачи участников форума MHP

Buratino

3

305

20 фев 2022, 10:34

Занимательная задача про взвешивание монет

в форуме Начала анализа и Другие разделы школьной математики

searcher

55

1242

17 фев 2023, 18:39

Занимательная задача на объём цилиндра

в форуме Геометрия

axelluch

2

110

16 май 2023, 17:11

Во сколько раз дороже? Занимательная арифметика

в форуме Интересные задачи участников форума MHP

FEBUS

9

516

16 мар 2018, 17:31

Определитель над полем или занимательная агрономия.

в форуме Линейная и Абстрактная алгебра

Surtr_RJ

1

423

10 ноя 2016, 16:40


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved