|
Уважаемые господа!
Я по складу ума - математик, а по образованию - экономист, но с недавних пор решил, что должен научиться программировать - это неотъемлемая часть моей будущей работы. Мой единственный опыт изучения языков программирования - это SQL. С недавних пор недолго думая среди многочисленных языков программирования для изучения я выбрал MatLab. Изучил синтаксис, порешал различные задачки. Но вот встретился с новым для себя типом задач, боюсь назвать этот тип как-то однозначно, но по-моему это динам-ое прогр-ие. Я уже нашел достаточно интересующих меня задач из этой области и во всех этих задачах для меня остается загадкой одно, пожалуй, самое интересное и важное место, это реализация процесса "путешествия" по "дереву", когда двигаешься по веточкам вглубь кроны и попадая в "тупик" приходится "отматывать" назад шаги и выбирать новое направление движения. Как мне кажется, с алгоритмами у меня проблем нет, я их сам придумываю и понимаю. Проблема в том, что я не знаю, как реализовать в плане синтаксиса такое "путешествие" по дереву...
Яркими примерами задач из данной области могут служить задачи о 8 ферзях или о лабиринте.
[8 ферзей: Расставить 8 ферзей на шах. доске так, чтоб они друг друга не били.
Лабиринт: обычный лабиринт с какого-нибудь детского журнала - надо найти выход]
Например, в задаче о 8 ферзях путешествие реализуется таким образом. 1-ого ферзя ставим в некоторую заранее определенную клетку на первой горизонтали. 2-ого ставим на второй горизонтали на самой левой клетке, что "свободна" (то есть, не под боем). 3-ого ставим на третьей горизонтали на самой левой клетке, что "свободна". И т.д.. Таким образом как бы тяготеем все время влево. Например, 7-ого ферзя оказалось негде ставить. Тогда наша программа должна отмотать на шаг назад и переставить 6-ого ферзя на следующую допустимую "свободную" клетку, а, если такой клетки не найдется, то сделать еще шаг назад и переставить 5-ого и т.д.
Например, в лабиринте мы начинаем с входа в него и из всех допустимых вариантов выбора направления движения выбираем самый левый. Если на каком-то шаге попали в тупик, то возвращаемся назад и выбираем другой самый левый вариант из оставшихся (то есть, кроме уже этого рокового) и идем дальше, а, если такового нет, то отматываем еще на шаг назад и т.д. И так пока не выходим из лабиринта или расставляем ферзей. При этом устроит хотя бы один вариант расстановки и выхода из лабиринта.
Проблема в том, что я не знаю какие команды использовать в MatLab для реализации такого "гуляния" по дереву. Если это все можно реализовать только при помощи
If, else, wfile, for, при помощи создания функций, рекурсий и т.д. то я сам, возможно, придумаю, просто дайте, пожалуйста, это знать. Если этих операторов мало, то скажите какие мне изучить еще. Например, я не имею нормального представления о работе команд break, continue, return, поскольку что в хелпе, что литературе им практически не уделяется внимание (разве что они уже используются в каких-то сложных примерах где мне, как новичку, не сильно понятно их действие)
P.S. По-моему такое "гуляние" по дереву называется backtracking. Я много находил объяснений и примеров этого понятия на других языках (как и решения этих задач), но не для MatLab. Также, поскольку мне нужно знание такого специфического синтаксиса для решения более сложных задач, может кто-нибудь со мной поделится программой для решения задачи о 8 ферзях или о лабиринте или им подобных написанных именно на MatLab (если кто решал). Мне очень важно разобраться в этом.
Заранее очень благодарен за любую помощь!
|
27.01.2009, 00:36 
