Zweidimensionale Tabelle in ein Array überführen und maximale Spalten ermitteln

Question

Hallo Leute,gemäß folgender Grafik habe ich folgendes zweidimensionale Array erstellt. Nur leider sind die Werte,welche mir die Klasse zurückliefert inkorrekt.Ich bekomme die Werte 6 und 2 zurück, möchte aber die Werte 3 und 4 haben. Eine Idee,wie ich das korrekt implementiere?

Hier die Grafik:

und hier der Code:

using System;
namespace IHK_Routen
{
    class Get_Routen
    {
        public int holeStreckeGewicht(string sb, string se)
        {
            Random zufall = new Random();
            int capacity = zufall.Next(1, 11);
            return capacity;
        }
        public int holeSteckePreis(string sb, string se)
        {
            Random zufall = new Random();
            int price = zufall.Next(10, 100);
            return price;
        }
        public int findeRoute(int gewicht,string[,]Routen)
        {
            int i = 0;
            //int minPreis = 0;
            //int minRoute=-1;
            int zeile_max = Routen.GetLength(0);//zeile_max der Tabelle,nicht des Arrays erwünscht
            int spalte_max = Routen.GetLength(1);//spalte_max der Tabelle,nicht des Arrays erwünscht
            Console.WriteLine("zeile_max:{0},spalte_max:{1}",zeile_max,spalte_max);
            return i;
        }
    }
}

using System;
namespace IHK_Routen
{
    class Program
    {
        static void Main(string[] args)
        {
            string[,] Routen = new string[6, 2] { { "A", "B" }, { "A", "C" },{"C","B"},
                                        { "A", "D" } , { "D", "E" }, { "E", "B" }  };
            Get_Routen berechnen = new Get_Routen();
            berechnen.findeRoute(10, Routen);
            Console.ReadLine();


        }
    }
}

Answer 1

Hi,
mit 6 und 2 werden die Anzahl der Elemente der 1. und 2. Dimension zurückgegeben.

Wie willst Du 3 und 4 als Ergebniswerte berechnen?

---

--
Viele Grüsse
Peter Fleischer (ehem. MVP)
Meine Homepage mit Tipps und Tricks

Answer 2

Das ist ja das Problem. Laut Pseudocode der IHK soll das wie folgt gehen:

von(j=0 solange i<anzahlZeilen(Routen)
.
.
.

Ich frage mich jetzt einfach,wie diese anzahlZeilen in C# implementiert werden sollen?

Hier die Fragestellung:

Und hier meine Lösung,die haut aber nicht hin:

using System;
namespace IHK_Routen
{
    class Get_Routen
    {
        public int holeStreckeGewicht(string sb, string se)
        {
            Random zufall = new Random();
            int capacity = zufall.Next(1, 11);
            return capacity;
        }
        public int holeSteckePreis(string sb, string se)
        {
            Random zufall = new Random();
            int price = zufall.Next(10, 100);
            return price;
        }
        public int findeRoute(int gewicht, string[,] Routen)
        {
            int i = 0;
            int minPreis = 0;
            int minRoute = -1;
            int zeile_max = Routen.GetLength(0) / 2;//ob das so stimmt,wage ich dann doch zu bezweifeln...
            int spalte_max = Routen.GetLength(1) * 2;
            for (i = 0; i < zeile_max; i++)
            {
                int preis = 0;
                bool abbruch = false;
                for (int j = 0; j < spalte_max - 1; j++)
                {
                    while (!abbruch&&Routen[i,j+1]!="")
                    {
                        if (gewicht > this.holeStreckeGewicht(Routen[i, j], Routen[i, j + 1]))
                        {
                            abbruch = true;
                        }
                        else
                        {
                            preis += this.holeSteckePreis(Routen[i, j], Routen[i, j + 1]);                           
                        }
                    }
                    if (preis < minPreis || minPreis == 0)
                    {
                        minPreis = preis;
                        minRoute = i;
                    }
                }
            }
            return minRoute;
        }
    }
}

using System;
namespace IHK_Routen
{
    class Program
    {
        static void Main(string[] args)
        {
            string[,] Routen = new string[6, 2] { { "A", "B" }, { "A", "C" },{"C","B"},
                                        { "A", "D" } , { "D", "E" }, { "E", "B" }  };
            Get_Routen berechnen = new Get_Routen();
            Console.WriteLine(berechnen.findeRoute(9, Routen));
            Console.ReadLine();
        }
    }
}

Answer 3

Hi,
die Aufgabenstellung ist so interessant, dass ich mich gleich mal daran versucht habe:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApp1
{
  class Program23
  {
    static void Main(string[] args)
    {
      try
      {
        Demo c = new Demo();
        c.Execute();
      }
      catch (Exception ex) { Console.WriteLine(ex.ToString()); }
      Console.WriteLine("Fertig, Abschluss mit beliebiger Taste");
      Console.ReadKey();
    }

    internal class Demo
    {
      internal void Execute()
      {
        string[,] Routen = new string[6, 2] { { "A", "B" }, { "A", "C" },{"C","B"},
                                        { "A", "D" } , { "D", "E" }, { "E", "B" }  };
        Get_Routen berechnen = new Get_Routen();
        Console.WriteLine(berechnen.findeRoute(1, Routen));
        Console.ReadLine();
      }
    }

    class Get_Routen
    {
      public decimal findeRoute(int gewicht, string[,] Routen)
      {
        // Abschnitte mit Parameterwerten belegen
        List<Abschnitt> abschnitte = new List<Abschnitt>();
        for (int i = 0; i <= Routen.GetUpperBound(0); i++)
          abschnitte.Add(new Abschnitt()
          {
            SB = Routen[i, 0],
            SE = Routen[i, 1],
            Gewicht = holeStreckeGewicht(Routen[i, 0], Routen[i, 1]),
            Preis = holeSteckePreis(Routen[i, 0], Routen[i, 1])
          });
        // Protokoll zur Kontrolle
        Debug.WriteLine("--- Ausgangswerte");
        foreach (Abschnitt a in abschnitte)
          Debug.WriteLine($"{a.SB} - {a.SE} {a.Gewicht} {a.Preis}");
        // Baum aufbauen bis SE = "B"
        List<Abschnitt> Baum = new List<Abschnitt>();
        foreach (Abschnitt a in abschnitte)
        {
          if (a.SB == "A") Baum.Add(a);
          findeAbschnitt(a);
        }
        // Liste der Routen ermitten
        List<List<Abschnitt>> routen = new List<List<Abschnitt>>();
        foreach (Abschnitt a in Baum) routenErmitteln1(a, routen);
        // Protokoll der Routen
        Debug.WriteLine("--- ermittelte Routen");
        foreach (List<Abschnitt> rs in routen)
        {
          Debug.WriteLine("--- Route");
          foreach (Abschnitt a in rs)
            Debug.WriteLine($"{a.SB} - {a.SE} {a.Summe}");
        }
        // Beste Route berechnen
        List<Abschnitt> besteRoute = (from r in routen orderby r.First<Abschnitt>().Summe select r).FirstOrDefault<List<Abschnitt>>();
        // Debug Anzeige der besten Route
        Debug.WriteLine("--- beste Route");
        foreach (Abschnitt a in besteRoute)
          Debug.WriteLine($"{a.SB} - {a.SE} {a.Preis}");
        Debug.WriteLine("");
       // Rückgabewert der besten Route
        return besteRoute.First<Abschnitt>().Summe;
        //
        // rekursiv Abschnitte zu einer Route finden
        void findeAbschnitt(Abschnitt a)
        {
          //if (a.SE == "B") return;
          foreach (Abschnitt b in abschnitte)
          {
            if (a.SE == b.SB)
            {
              Abschnitt c = b.Copy();
              a.Next.Add(c);
              c.Parent = a;
              findeAbschnitt(c);
            }
          }
        }
        // rekursiv Routen im Baum vorwärts ermitteln
        void routenErmitteln1(Abschnitt a, List<List<Abschnitt>> rs)
        {
          if (a.Gewicht < gewicht) return;
          a.Summe += a.Preis;
          if (a.SE == "B")
          {
            List<Abschnitt> r = new List<Abschnitt>();
            routenErmitteln2(a, r, rs);
          }
          foreach (Abschnitt b in a.Next)
          {
            b.Summe = a.Summe;
            routenErmitteln1(b, rs);
          }
        }
        // recursiv Route rückwärts aus dem Baum extrahieren
        void routenErmitteln2(Abschnitt a, List<Abschnitt> r, List<List<Abschnitt>> rs)
        {
          r.Insert(0, a);
          if (a.Parent == null) rs.Add(r);
          else
          {
            a.Parent.Summe = a.Summe;
            routenErmitteln2(a.Parent, r, rs);
          }
        }
      }

      internal class Abschnitt
      {
        internal string SB { get; set; }
        internal string SE { get; set; }
        internal int Gewicht { get; set; }
        internal decimal Preis { get; set; }
        internal decimal Summe { get; set; } = 0;
        internal List<Abschnitt> Next { get; set; } = new List<Abschnitt>();
        internal Abschnitt Parent { get; set; }
        internal Abschnitt Copy()
        {
          return new Abschnitt()
          {
            SB = this.SB,
            SE = this.SE,
            Gewicht = this.Gewicht,
            Preis = this.Preis
          };
        }
      }

      Random zufall = new Random();
      internal int holeStreckeGewicht(string sb, string se) => zufall.Next(10, 50);
      internal decimal holeSteckePreis(string sb, string se) => zufall.Next(1000, 10000) / 100;
    }
  }
}

---

--
Viele Grüsse
Peter Fleischer (ehem. MVP)
Meine Homepage mit Tipps und Tricks

Answer 4

Deine Lösung ist weit über dem,was die IHK verlangte. Eine Kleinigkeit ist jedoch inkorrekt.Das fiel mir erst vor kurzem auf: Das Array muss wie folgt initialisiert werden:

          string[,] Routen = new string[3, 4] { { "A", "B","","" }, { "A", "C","B",""},
                                        { "A", "C" , "D", "E" } };

Answer 5

Hi,
ich hatte die Frage aber anders verstanden, mich gewundert, dass die IHK solche komplexen Fragestellungen stellt und aus reinem Interesse mal solch eine Routenoptimierung programmiert.

Mit der neuen Array-Darstellung vereinfacht sich die Problemlösung, da die möglichen Routen nicht ermittelt werden müssen, sondern jede Route nur geprüft werden muss. Problematisch bei der neuen Darstellung der Routen ist, dass der 3. Eintrag nicht im "B" endet. Wie soll da verfahren werden? Auch gibt es im 2. und 3. Eintrag den gleichen Abschnitt A-C. Wenn da die gleichen Parameter Preis und Gewicht genommen werden müssen, dann geht das nicht mit dem jetzigen Aufruf und einer Zufallszahl.

---

--
Viele Grüsse
Peter Fleischer (ehem. MVP)
Meine Homepage mit Tipps und Tricks