88 lines
2.4 KiB
C#
88 lines
2.4 KiB
C#
using System;
|
|
using System.Collections.Generic;
|
|
using System.Linq;
|
|
|
|
namespace Keres
|
|
{
|
|
public class Feladat<T>
|
|
{
|
|
public T Kezdo { get; }
|
|
public T Cel { get; protected set; }
|
|
|
|
public Feladat(T kezdo, T cel)
|
|
{
|
|
Kezdo = kezdo;
|
|
Cel = cel;
|
|
}
|
|
|
|
public virtual bool Celteszt(T allapot)
|
|
{
|
|
return EqualityComparer<T>.Default.Equals(allapot, Cel);
|
|
}
|
|
public virtual IEnumerable<(string, T)> Rakovetkezo(T allapot){
|
|
throw new NotImplementedException();
|
|
}
|
|
|
|
public virtual int Utkoltseg(int c, T allapot1, string lepes, T allapot2)
|
|
{
|
|
return c + 1;
|
|
}
|
|
}
|
|
|
|
|
|
public class Csucs<T>
|
|
{
|
|
public T Allapot { get; } // The state of this node
|
|
public Csucs<T>? Szulo { get; } // Parent node
|
|
public string? Lepes { get; } // Action taken to reach this node
|
|
public int Utkoltseg { get; } // Path cost (g(n))
|
|
public int Melyseg { get; } // Depth in the tree
|
|
|
|
|
|
public Csucs(T allapot, Csucs<T>? szulo = null, string? lepes = null, int utkoltseg = 0)
|
|
{
|
|
Allapot = allapot;
|
|
Szulo = szulo;
|
|
Lepes = lepes;
|
|
Utkoltseg = utkoltseg;
|
|
Melyseg = szulo?.Melyseg + 1 ?? 0;
|
|
}
|
|
|
|
public override string ToString()
|
|
{
|
|
return $"<Csucs: {Allapot}>";
|
|
}
|
|
|
|
/// <summary>
|
|
/// Returns the path from the root to this node.
|
|
/// </summary>
|
|
public List<Csucs<T>> Ut(){
|
|
List<Csucs<T>> valasz = new List<Csucs<T>>();
|
|
|
|
for(Csucs<T>? x = this; x != null; x = x.Szulo){
|
|
valasz.Add(x);
|
|
}
|
|
|
|
valasz.Reverse();
|
|
|
|
return valasz;
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Returns the sequence of steps taken to reach this node.
|
|
/// </summary>
|
|
public List<string?> Megoldas(){
|
|
return Ut().Skip(1).Select(csucs => csucs.Lepes).ToList();
|
|
}
|
|
|
|
public IEnumerable<Csucs<T>> Kiterjeszt(Feladat<T> feladat){
|
|
foreach(var (muvelet, kovetkezo) in feladat.Rakovetkezo(Allapot)){
|
|
if(!Ut().Select(csucs => csucs.Allapot).Contains(kovetkezo)){
|
|
yield return new Csucs<T>(kovetkezo, this, muvelet, feladat.Utkoltseg(Utkoltseg, Allapot, muvelet, kovetkezo));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
} |