Я учусь решать различные задачи на поиск опимального варианта.
Для примера взял задачу: есть поле n*m клеток в каждой клетке случайно число от 1 до 5.
За один ход мы можем пойти либо вправо либо вниз. Стартовая точка(1,1). Конечная точка(n,m).
Нужно найте такой вариант прохождения при котором мы наберем макс. кол-во очков, неважно за сколько ходов.
Вот мое решение:
- Код: Выделить всё
Type findoneel
t As Integer
s As Integer
p As String
End Type
Type findonetmpel
x As Byte
y As Byte
s As Integer
p As String
End Type
Private s() As Byte
Public Sub findone(n As Byte, m As Byte)
ReDim s(n, m) As Byte
sgenerate n, m
Dim curV() As findonetmpel
Dim newV() As findonetmpel
Dim vars() As findoneel
Dim vC As Integer
Dim xC As Integer
Dim yC As Integer
Dim tC As Integer
Dim cC As Integer
Dim out As String
Dim bone As Integer
vC = 0
tC = 0
ReDim newV(1) As findonetmpel
newV(1).x = 1
newV(1).y = 1
newV(1).s = s(1, 1)
Do
ReDim curV(UBound(newV)) As findonetmpel
curV = newV
ReDim newV(1) As findonetmpel
cC = 0
For xC = 1 To UBound(curV)
If curV(xC).x = n And curV(xC).y = m Then
vC = vC + 1
ReDim Preserve vars(vC) As findoneel
vars(UBound(vars)).s = curV(xC).s
vars(UBound(vars)).t = tC
vars(UBound(vars)).p = curV(xC).p
End If
If curV(xC).x < n Then
cC = cC + 1
ReDim Preserve newV(cC) As findonetmpel
newV(cC).x = curV(xC).x + 1
newV(cC).y = curV(xC).y
newV(cC).s = curV(xC).s + s(newV(cC).x, newV(cC).y)
newV(cC).p = curV(xC).p & ">;"
End If
If curV(xC).y < m Then
cC = cC + 1
ReDim Preserve newV(cC) As findonetmpel
newV(cC).x = curV(xC).x
newV(cC).y = curV(xC).y + 1
newV(cC).s = curV(xC).s + s(newV(cC).x, newV(cC).y)
newV(cC).p = curV(xC).p & "\/;"
End If
Next xC
tC = tC + 1
If cC = 0 Then Exit Do
Loop
bone = 1
For xC = 1 To UBound(vars)
If vars(xC).s > vars(bone).s Then bone = xC
Next xC
End Sub
В результате получаем что vars(bone).s я вляется ответом. Работает гдето при m<9 и n<9.
Разумеется если проставить vC и cC пременные как Long то все буте работать и при ста, но только результат будет через столько-же лет.
А теперь мои вопросы:
1) Насколько плохо я написал алгоритм перебора всех значений?
2) Какие алгоритмы могут дать точно верное решение быстрее по времени вычисления?
3) Какие алгоритмы могут дать точно верное решение при меньшем объеме кода?
Эвристический не подходит так-как не всегда выдает самое лучшее решение.
4) я слышал о гинетических алгоритмах и нейронных сетях. Объясните пожалуста если несложно.
Или лучше дайте ссылки на сайты где об этом подробно и доступно
написанно(особенно о генетическом алгоритме). А то я читал про нейронные сети, я то понял что это такое
и как работает но не понимаю как это использовать для поиска оптимального варианта.
Заранее всем огромная благодарность.
